When data packets are sent in a network, the data packets are routed from a sending computer through one or more routers and/or switches to a destination computer. Processing of the data packets by the routers typically involves looking up data using a key. For example, the data packet typically includes a destination address of the data packet. Network devices such as routers and switches may use the destination address to lookup a next_hop address of a next router or switch on a path to the destination address. The next_hop value may be any number of things such as the physical port on which the packet should be transmitted in order to reach its destination in the network or some other packet processing direction.
The destination address may include 48 bits. One approach for handling the data lookup by the router or switch uses memory having 248 locations. However, this approach is typically impractical due to the cost of the memory and is an inefficient use of memory since the entire address space is not used. Referring now to FIG. 1, another approach uses a hash function generator 10 that generates a hash value based upon the input address, which may be the destination address or any other key. The hash value corresponds to a physical address of the data in memory 14. In the router/switch example, the data includes the destination address and the next_hop address. A comparing module 16 compares the data returned from the physical address to the input address to determine whether there is a match. If a match occurs, the data is returned.
The hash function generator 10, however, does not generate a unique hash value for each of the potential input addresses. For example, the memory location may already be occupied by another input address and its associated next hop. Therefore, the data that is returned by the memory 14 may not match the input address and a “collision” occurs. Collisions increase the amount of time that is required to lookup the data and find a match. When a collision occurs, the physical address is usually incremented by the comparing module 16 and the data at the new physical address is compared to the input address. If a match occurs, the data is returned. If a match does not occur (another collision), the physical address is incremented and the data is retrieved and compared to the input address. The process is repeated until a match occurs or a predefined limit of attempts is reached (at which point the algorithm will halt and the address cannot be learned by the device implementing the hash function).
Referring now to FIG. 2, steps that are performed using the hash function lookup approach are shown generally at 20. Control begins in step 22. In step 24, control determines whether an input address is received. If not, control returns to step 24. If step 24 is true, the hash function generator 10 generates a hash value or physical address for the input address in step 26. In step 28, data is retrieved from the physical address in the memory 14. In step 32, the comparing module 16 determines whether the input address matches the returned data. If not, the physical address is incremented in step 34 and control returns to step 28. If step 32 is true, the matching data is returned in step 34 and control continues with step 24. As can be appreciated, the loop containing steps 28, 32 and 34 may be repeated multiple times when a collision occurs, which may cause delays. This delay may stall the lookup hardware to a point where it cannot keep up with the rate of the incoming traffic and packets may be lost.
Referring now to FIG. 3, another approach employs content addressable memory (CAM) 50, which is physical memory that is designed for matching. Data having an address that matches an input address is returned. The CAM matches the input address bit-by-bit with all entries in the CAM 50 in a parallel fashion (which typically means—in single clock cycle of the CAM device) and returns the first matching address.
The CAM 50 provides guaranteed performance. In other words, the address lookup will take a fixed amount of time. While CAM 50 provides the highest performance, the use of CAM 50 is typically very expensive and consumes more power than the memory 14 that is used for the hash function lookup approach. The hash function lookup approach is less costly, but does not guarantee that the lookup will take a fixed amount of time. In other words, the hash function lookup approach cannot guarantee the number of lookups that will be required. In some applications such as switches and routers in network applications, performance specifications may require guaranteed lookup performance times so that a predetermined wire speed is guaranteed, while maintaining low cost and limiting power consumption.